package com.fengdi.book.easy;

import java.util.Arrays;

public class SortAndSearch {
    public static class Merge {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            if (n == 0) return;
            int[] result = new int[m + n];
            int i = 0;
            int j = 0;
            int k = 0;

            while (i < m && j < n) {
                if (nums1[i] < nums2[j]) {
                    result[k++] = nums1[i++];
                }else {
                    result[k++] = nums2[j++];
                }
            }

            while(i < m) {
                result[k++] = nums1[i++];
            }

            while(j < n) {
                result[k++] = nums2[j++];
            }

            System.arraycopy(result, 0, nums1, 0, n + m);

        }
    }

    public static class FirstBadVersion {
        private boolean isBadVersion(int version) {
            return version >= 4;
        }

        public int firstBadVersion(int n) {
            if(n <= 0) return -1;

            // 正常遍历会超时，进行二分查找
            int left = 1, right = n;
            while(left < right) {
                int mid = left + (right - left) / 2;
                System.out.println(left + (right - left) / 2);
                System.out.println((left + right) / 2);
                if(isBadVersion(mid)) {
                    right = mid;
                }else {
                    left = mid + 1;
                }
            }
            return left;
        }
    }
}
